#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define SElemType int
#define Status int

// 链栈是 运算受限 的单链表，只能在链表头部进行操作
typedef struct StackNode{
	SElemType data;
	struct StackNode *next;
}StackNode, *LinkStack;
//LinkStack S;

//链表的头指针就是栈顶
//不需要头结点
//基本不存在栈满的情况
//空栈相当于头指针指向空
//插入和删除仅在栈顶处执行 

//算法3.5 链栈的初始化 
Status InitStack(LinkStack &S){
	//构造一个空栈，栈顶指针置为空
	S = NULL;
	return OK; 
}

//判断链栈是否为空 
Status StackEmpty(LinkStack S){
	if(S == NULL) return TRUE;
	else return FALSE;
}

Status Push(LinkStack &S, SElemType e){
	StackNode *p = new StackNode; //生成新结点P
	p->data = e; //将新结点数据域置为e 
	p->next = S; //将新结点插入栈顶 
	S = p; 		 //修改栈顶指针 
	return OK;
}

Status Pop(LinkStack &S, SElemType &e){
	if(S == NULL) return ERROR;
	e = S->data;
	StackNode *p = S;
	S = S->next;
	delete(p);
	return OK;
}

//取栈顶元素 
SElemType GetTop(LinkStack S){
	if(S != NULL)
		return S->data;
} 

//以下三种情况常常用到递归方法 
//1. 递归定义的数学函数 
//2. 具有递归特性的数据结构 
//3. 可递归求解的问题 
 
//递归问题：用分治法求解 
//分治法求解递归问题算法的一般形式 
//void p(参数表){
//	if (递归结束条件)  可直接求解步骤;   -----基本项 
//	else p(较小的参数);  				 -----归纳项 
//} 

//递归的优缺点
//优点：结构清晰，程序易读
//缺点：每次调用都要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。 

//递归 --> 非递归 
//方法1：尾递归、单向递归->循环结构
//方法2：自用栈模拟系统的运行时栈 

int main(void)
{
	LinkStack S;
	InitStack(S);
	int is_empty = StackEmpty(S);
	cout<<"is_empty = "<<is_empty<<"\n";
	cout<<"链栈学习中...\n请输入你要创建的结点个数：";
	int length;
	cin>>length;
	for(int i = 1; i <= length; i++){
		printf("请输入第%d个结点的值：",i);
		SElemType data;
		cin>>data;
		Push(S, data);
		is_empty = StackEmpty(S);
		cout<<"is_empty = "<<is_empty<<"\n";
	}
	puts("输入完毕");
	while(length){
		length--;
		printf("还剩%d个结点，弹出数据：", length); 
		SElemType e;
		Pop(S, *&e);
		cout<<e;
		puts("");
	} 
	return 0;
}